package com.javabasic.algorithm.leetcode;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/6/8 22:03
 * @link [807. 保持城市天际线 - 力扣（LeetCode）](https://leetcode.cn/problems/max-increase-to-keep-city-skyline/)
 */
public class MaxIncreaseToKeepCitySkyline {

    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int len = grid.length;

        int[] colMax = new int[len];
        int[] rowMax = new int[len];

        int colMaxValue;
        int rowMaxValue;

        /**
         * 找出每行每列的最大值
         */
        for (int i = 0; i < len; i++) {
            colMaxValue = Integer.MIN_VALUE;
            rowMaxValue = Integer.MIN_VALUE;
            for (int j = 0; j < len; j++) {
                if (grid[i][j] > rowMaxValue) {
                    rowMaxValue = grid[i][j];
                }
                if (grid[j][i] > colMaxValue) {
                    colMaxValue = grid[j][i];
                }
            }
            colMax[i] = colMaxValue;
            rowMax[i] = rowMaxValue;
        }


        /**
         * 为一个位置可以扩展的最大值为 grid[i][j]-max(rowMax[i],colMax[j])
         */
        int result = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                result += Math.abs(grid[i][j] - Math.min(rowMax[i], colMax[j]));
            }
        }

        return result;
    }
}
